package org.example.myleet.p938;

import org.example.myleet.Utils.TreeNode;

/**
 * 1~2 ms
 * Morris中序遍历加一点点变化，做了剪枝
 */
public class Solution {
    public int rangeSumBST(TreeNode root, int low, int high) {
        int result = 0;
        TreeNode cur = root;
        while (cur != null) {
            if (cur.left != null) {
                TreeNode prev = cur.left;
                while (prev.right != null && prev.right != cur) {
                    prev = prev.right;
                }
                if (prev.right == cur || prev.val < low) {
                    //prev.val < low 对左边的更小的节点剪枝
                    prev.right = null;
                    if (cur.val >= low && cur.val <= high) {
                        result += cur.val;
                    }
                    cur = cur.right;
                } else {
                    prev.right = cur;
                    cur = cur.left;
                }
            } else {
                if (cur.val >= low && cur.val <= high) {
                    result += cur.val;
                }
                if (cur.val > high) {
                    //cur.val > high 对右边的更大的节点剪枝
                    cur = null;
                } else {
                    cur = cur.right;
                }
            }
        }
        return result;
    }
}
